#include <util.h>
#include "heapsort.h"

/*
void swap(int *a, int *b)
{
    *a = *a ^ *b;
    *b = *a ^ *b;
    *a = *a ^ *b;
}
*/

/* assume the binary trees rooted at LEFT(i) and RIGHT(i)
 * are already max heaps, only a[i] may be smaller than 
 * its children, thus violating the max-heap property.
 * This procedure let the value at a[i] float down in the
 * max-heap so that the subtree rooted at index i becomes 
 * a max-heap.
 */
void max_heapify(int a[], int n, int i)
{
    int largest, r, l;

    r = RIGHT(i);
    l = LEFT(i);
    if (l < n && a[l] > a[i])
    {
	largest = l;
    }
    else
    {
	largest = i;
    }

    if (r < n && a[r] > a[largest])
    {
	largest = r;
    }

    if (largest != i)
    {
	swap(&a[i], &a[largest]);
	max_heapify(a, n, largest);
    }
}

void build_max_heap(int a[], int n)
{
    int i;

    for (i = n / 2 - 1; i >= 0; i--)
    {
	max_heapify(a, n, i);
    }
}

void heapsort(int a[], int n)
{
    int i;

    build_max_heap(a, n);
    for (i = n - 1; i >= 1; i--)
    {
	//print_a(a, n);
	swap(&a[0], &a[i]);
	max_heapify(a, i, 0);
    }
}

void bubblesort(int a[], int n)
{
    int i, j;

    for (i = 0; i < n - 1; i++)
    {
	for (j = i + 1; j < n; j++)
	{
	    if (a[j] < a[i])
		swap(&a[j], &a[i]);
	}
    }
}
